|
In computer science, the Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.The algorithm was conceived in 1974 by Donald Knuth and Vaughan Pratt, and independently by James H. Morris. The three published it jointly in 1977. ==Background== A string matching algorithm wants to find the starting index m in string S. If the index m reaches the end of the string then there is no match, in which case the search is said to "fail". At each position m the algorithm first checks for equality of the first character in the word being searched, i.e. S() =? W(). If a match is found, the algorithm tests the other characters in the word being searched by checking successive values of the word position index, i. The algorithm retrieves the character W() in the word being searched and checks for equality of the expression S() =? W(). If all successive characters match in W at position m, then a match is found at that position in the search string.Usually, the trial check will quickly reject the trial match. If the strings are uniformly distributed random letters, then the chance that characters match is 1 in 26. In most cases, the trial check will reject the match at the initial letter. The chance that the first two letters will match is 1 in 262 (1 in 676). So if the characters are random, then the expected complexity of searching string S is 1000 characters, then the string search should complete after about one billion character comparisons.That expected performance is not guaranteed. If the strings are not random, then checking a trial m may take many character comparisons. The worst case is if the two strings match in all but the last letter. Imagine that the string S is ''n'', then the worst-case performance is ''O''(''k''⋅''n'').The KMP algorithm has a better worst-case performance than the straightforward algorithm. KMP spends a little time precomputing a table (on the order of the size of W, it will increment m by 1, but it will know that the first 998 characters at the new position already match. KMP matched 999 ''A'' characters before discovering a mismatch at the 1000th character (position 999). Advancing the trial match position m by one throws away the first ''A'', so KMP knows there are 998 ''A'' characters that match W[] and does not retest them; that is, KMP sets i to 998. KMP maintains its knowledge in the precomputed table and two state variables. When KMP discovers a mismatch, the table determines how much KMP will increase (variable m) and where it will resume testing (variable i).抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Knuth–Morris–Pratt algorithm」の詳細全文を読む スポンサード リンク
|